package 我的Java学习_算法基础.day_08;

import java.util.ArrayList;

/**
 * @author 挚爱之夕
 * @date 2021/8/26 - 08 - 26 - 9:06
 * @Description: 我的Java学习.day_08
 * @Version: 1.0
 */
public class _135_最长公共子序列 {
    public static void main(String[] args) {
        String s1 = "A4B34C",s2 = "A87C";
        ArrayList ans = dfs(s1,s2);
        System.out.println(ans);
        String s = dpSolution(s1,s2);
        System.out.println(s);
    }
    //深度搜索
    private static ArrayList<Character> dfs(String s1,String s2){
        int len1 = s1.length();
        int len2 = s2.length();
        ArrayList<Character> ans = new ArrayList<>();
        for (int i = 0; i < len1; i++) {
            //求以i字符开头的公共子序列
            ArrayList<Character> list = new ArrayList<>();
            //和s2的每个字符比较
            for (int j = 0; j < len2; j++) {
                if(s1.charAt(i)==s2.charAt(j)){//若果相同
                    list.add(s1.charAt(i));
                    list.addAll(dfs(s1.substring(i+1),s2.substring(j+1)));
                    break;
                }
            }
            if(list.size()>ans.size())
                ans = list;
        }
        return ans;
    }
    //动态规划
    static String dpSolution(String s1,String s2){
        int len1 = s1.length();
        int len2 = s2.length();
        int[][] dp = new int[len1+1][len2+1];//动规数组
        int flag = 0;
        //初始化第一列
        //O(M)
        for (int i = 1; i <=len1 ; i++) {
            if(flag==1){    //前面有一个相同，后面都为1
                dp[i][1] = 1;
            }else if(s1.charAt(i-1)==s2.charAt(0)){//第一次匹配相同
                dp[i][1] = 1;
                flag = 1;
            }else{
                dp[i][1] = 0;
            }
        }
        flag = 0;
        //初始化第一行
        //O(N)
        for(int j = 1;j<=len2;j++){
            if(flag==1){
                dp[1][j] = 1;
            }else if(s2.charAt(j-1)==s1.charAt(0)){
                dp[1][j] = 1;
                flag = 1;
            }else{
                dp[1][j] = 0;
            }
        }
        //O(M*N)
        for(int i = 2;i<=len1;i++){//M
            for(int j = 2;j<=len2;j++){//N
                //左和上中取最大
                int maxOfLeftAndUp = Math.max(dp[i-1][j],dp[i][j-1]);
                if(s1.charAt(i-1)==s2.charAt(j-1)){
                    //左、上最大和左上角中取最大
                    dp[i][j] = Math.max(maxOfLeftAndUp,dp[i-1][j-1]+1);
                }else{
                    dp[i][j] = maxOfLeftAndUp;
                }
            }
        }
        return parseDp(dp,s1,s2);
    }

    private static String parseDp(int[][] dp, String s1, String s2) {
        int M = s1.length();
        int N = s2.length();
        StringBuilder sb = new StringBuilder();
        while(M>0&&N>0){
            //比左和上大，一定是当前位置的字符相等
            if(dp[M][N]>Math.max(dp[M-1][N],dp[M][N-1])){
                sb.insert(0,s1.charAt(M-1));
                M--;
                N--;
            }else{//一定选择的是左边和上边的大者
                if (dp[M-1][N]>dp[M][N-1]) {
                    M--; //往上移
                }else{
                    N--; //往左移
                }

            }
        }
        return sb.toString();
    }

}
